//
// Created by Eric on 2023/1/21.
// 管理所有天体的数据库
//

#ifndef UUU_ASOBJECTSET_H
#define UUU_ASOBJECTSET_H
#include <unordered_map>
#include <unordered_set>
#include "AsObject.h"
#include "uuu_utility.h"
#include "Counter.h"

class AsObjectSet {
public:
    // api
    // 初始化函数。生成原初天体
    void Initialize(DatabaseInfo* p_dbi);

    // TODO 这个可以提前算好的
    // 返回id为a和b两个天体之间的距离
    double GetDistance(int a, int b);

public:
    // 构造方法
    AsObjectSet() = default;

private:
    // data
    std::unordered_map<int, AsObject> asobjects;
    DatabaseInfo* p_dbi_;

public:
    // 迭代器
    auto begin(){ return asobjects.begin();}
    auto end(){return asobjects.end();}
};

double AsObjectSet::GetDistance(int a, int b){
    const auto& lhs = asobjects[a].coord();
    const auto& rhs = asobjects[b].coord();

    double X = lhs.x - rhs.x;X *= X;
    double Y = lhs.y - rhs.y;Y *= Y;
    double Z = lhs.z - rhs.z;Z *= Z;

    return sqrtf(static_cast<float>(X) + static_cast<float>(Y) + static_cast<float>(Z));
}

void AsObjectSet::Initialize(DatabaseInfo* p_dbi) {
    p_dbi_ = p_dbi;
//    auto noa = dbi.num_of_asobject;
//    // 生成noa个天体并且设置拥有关系
//    // 多余的天体的cz_idx被设置为-1
//    for(int ao_idx = 0;ao_idx < noa;ao_idx++){
//        int cz_idx = ao_idx >= dbi.num_of_civilization ? -1 : ao_idx;
//        asobjects[ao_idx] = AsObject::CreateAsObject(Counter::first_resource(), Counter::first_coord(dbi.universe_size), cz_idx);
//    }

// 测试用
    asobjects[0] = AsObject::CreateAsObject("a",1000, Coord(0,0,0), 0);
    asobjects[1] = AsObject::CreateAsObject("b",2000, Coord(0,3,0), 1);
    asobjects[2] = AsObject::CreateAsObject("c",1500, Coord(3,3,0),2);
    asobjects[3] = AsObject::CreateAsObject("d",500, Coord(5,3,0),3);
    asobjects[4] = AsObject::CreateAsObject("e",2000, Coord(5,5,0),4);
    asobjects[5] = AsObject::CreateAsObject("f",1500, Coord(3,0,0), -1);
    asobjects[6] = AsObject::CreateAsObject("g",1500, Coord(5,0, 0), -1);
    asobjects[7] = AsObject::CreateAsObject("h",1500, Coord(0,5,0), -1);
    asobjects[8] = AsObject::CreateAsObject("i",1500, Coord(3,5,0), -1);
}

#endif //UUU_ASOBJECTSET_H


#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <windows.h>


using namespace std;

vector<int> datas;

// 测量函数运行时间
typedef void(*TestFunc)();
double GetFuncRunTime(TestFunc test_func){
    LARGE_INTEGER  t1,t2,tc;
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&t1);

    test_func();

    QueryPerformanceCounter(&t2);
    double time = static_cast<double>(t2.QuadPart - t1.QuadPart) / static_cast<double>(tc.QuadPart);
    return time;
}

int Partition(std::vector<int>& arr, int left, int right) {
    int base = arr[left];
    int i = left, j = right + 1;
    while (true) {
        while (arr[++i] < base) {
            if (i == right)
                break;
        }
        while (arr[--j] > base) {
            if (j == left)
                break;
        }
        if (i >= j) {
            break;
        }
        swap(arr[i], arr[j]);
    }
    swap(arr[left], arr[j]);
    return j;
}

void QuickSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = Partition(arr, left, right);
    QuickSort(arr, left, mid - 1);
    QuickSort(arr, mid + 1, right);
}

void Test(){
    QuickSort(datas, 0, datas.size() - 1);
}

int main(){
    // 读取数据
    ifstream fin;
    fin.open("disorderWithoutRepetition10000.txt");
    int num;
    while(fin >> num){
        datas.push_back(num);
    }
    fin.close();

    // 测试时间
    cout << GetFuncRunTime(Test);

    // 写入文件
    ofstream fout("result.txt");
    for (auto i : datas){
        fout <<i <<' ';
    }
    fout.close();

    return 0;
}

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

void generateGrayCode(vector<string>& grayCode, string& curCode, int index, int n) {
    // 如果当前二进制码长度等于n，将其添加到格雷码vector中
    if (curCode.size() == n) {
        grayCode.push_back(curCode);
        return;
    }

    // 递归生成下一位的格雷码
    generateGrayCode(grayCode, curCode, index + 1, n);

    // 将当前位的二进制码取反
    curCode[index] = (curCode[index] == '0') ? '1' : '0';

    // 递归生成下一位的格雷码
    generateGrayCode(grayCode, curCode, index + 1, n);
}

int main() {
    int n;
    scanf("%d", &n);

    if (n <= 0) {
        printf("n should be greater than 0.\n");
        return 0;
    }

    // 生成n位格雷码
    vector<string> grayCode;
    string curCode(n, '0');
    generateGrayCode(grayCode, curCode, 0, n);

    // 输出n位格雷码
    for (int i = 0; i < grayCode.size(); i++) {
        cout << grayCode[i] << " ";
    }
    cout << endl;

    return 0;
}
